package hot

/*
*
原题链接:
https://leetcode.cn/problems/decode-string/description/

394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

思路:
方法1: 栈
如果是数字: 将数字字符转化为整数, 用于后续倍数计算
如果是字符: 延长当前字符串
如果是左括号: 当前状态入栈
如果是右括号: 弹出状态, 组合字符串

假设:
3 [ a 2 [ c ] ]

stack (3,"") (2,"a")
res = "acc"
multi = 2

优化解题方法:
每次遇到左括号,剩余的字符串,基本构成一个和原始字符串结构一致的子串
也是由起始数字和字符组成的问题

模式识别: 一旦碰到结构和原问题一致的子问题, 可以递归调用函数解决

当函数返回时, 和现在的字符串组合一下, 就可以获得原问题的解
递归函数中, 遍历剩余的字符串, 如果是整数, 就继续计算倍数
如果是左括号, 递归解决子问题, 并且把子问题的结果和当前结果组合起来, 获得原问题的解
如果是右括号, 说明当前问题解决完毕, 返回状态, 这里的状态包括目前解码的字符串和处理位置i
*/

func decodeString(s string) string {
	times := make([]int, 0)         // 数字次数栈
	preStrings := make([]string, 0) // 本轮 倍数*[]之前的字符

	res := "" // 声明结果
	time := 0 // 声明次数计数

	for _, c := range s { // 遍历字符串
		if isNum(byte(c)) { // 如果是数字, 那么 time*10 + 当前数字
			time = time*10 + int(c-'0')
		} else if c == '[' { // 如果遇到左括号
			times = append(times, time)          // [前的倍数入栈
			preStrings = append(preStrings, res) // [前的字符串入栈

			time = 0 // 重置
			res = ""
		} else if c == ']' {
			curTime := times[len(times)-1] // 上轮的次数
			times = times[:len(times)-1]   // 移除上轮的次数

			preStr := preStrings[len(preStrings)-1]     // 上轮的字符串
			preStrings = preStrings[:len(preStrings)-1] // 移除上轮的字符串

			for curTime > 0 { // 2次
				preStr += res // a = a + c
				curTime--     // 次数--
			}
			res = preStr // res置新为previousString
		} else { // 如果是字符, 那么就加入res
			res += string(c)
		}
	}

	return res
}

func isNum(c byte) bool {
	return c >= '0' && c <= '9'
}
